/**
    ******************************************************************************
    * @file    link.c
    * @author  debian
    * @version V1.0.0
    * @date    2019-11-24
    * @brief   链表相关的代码
    ******************************************************************************
    * @attention
    *
    *
    ******************************************************************************
    */ 

/* Includes ------------------------------------------------------------------*/
#include "link.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


/** @addtogroup DataStruct_Driver
    * @{
    */



/** @addtogroup link
    * @{
    */

/* Private typedef -----------------------------------------------------------*/

/* Private define ------------------------------------------------------------*/

/* Private macro -------------------------------------------------------------*/

/* Private variables ---------------------------------------------------------*/

/* Private function prototypes -----------------------------------------------*/

/* Private functions ---------------------------------------------------------*/


/** @defgroup link_Exported_Functions link Exported Functions
    * @{
    */

/** @defgroup link_Exported_Functions_Group1 Initialization and deinitialization functions
    *  @brief    Initialization and Configuration functions
    *
@verbatim    
    ===============================================================================
                ##### Initialization and deinitialization functions #####
    ===============================================================================
    [..]
        This section provides functions allowing to initialize and de-initialize the link
        to be ready for use.
 
@endverbatim
    * @{
    */ 

/**
    * @brief  创建link对象
    * @param  
    * @retval 
    */ 
    int single_link_creat(struct single_link **link)
    {
		//申请头节点
		*link = (struct single_link *)malloc(sizeof(struct single_link));
		if(link == NULL)
			return -1;
				
		(*link)->data = 0;		//头节点的data,表示长度

		return 0;
    }

/**
    * @brief  销毁link对象
    * @param  
    * @retval 
    */ 
    int single_link_destroy(struct single_link **link)
    {
		if(*link == NULL)
			return 0;

		free(*link);
		*link = NULL;

		return 0;
    }
    
/**
    * @}
    */

/** @defgroup link_Exported_Functions_Group2 operation functions 
    *  @brief   operation functions
    *
@verbatim   
    ===============================================================================
                        ##### operation functions #####
    ===============================================================================
    [..]
        This subsection provides a set of functions allowing to manage the link.

@endverbatim
    * @{
    */

	/**
		* @brief  单链表尾部添加
		* @param  
		* @retval 
		*/ 
		int single_link_tail_add(struct single_link *link, Elemtype item)
		{
			//申请一个新节点
			struct single_link *node = NULL;
			node = (struct single_link *)malloc(sizeof(struct single_link));
			if(node == NULL)
				return -1;
				
			node->data = item;		//填充数据


			//遍历数据，找到尾节点
			struct single_link * pNext = link;
			while(pNext->next != NULL)  //不等于空继续循环
			{
				pNext = pNext->next;
			}

			//现在执行插入操作
			node->next = pNext->next;
			pNext->next = node;
			link->data++;
			
			return 0;
		}


	/**
		* @brief  单链表头部添加
		* @param  
		* @retval 
		*/ 
		int single_link_head_add(struct single_link *link, Elemtype item)
		{
			//申请一个新节点
			struct single_link *node = NULL;
			node = (struct single_link *)malloc(sizeof(struct single_link));
			if(node == NULL)
				return -1;
				
			node->data = item;		//填充数据

			//头节点
			struct single_link * pNext = link;

			//现在执行插入操作
			node->next = pNext->next;
			pNext->next = node;
			link->data++;
			
			return 0;
		}

	/**
		* @brief  删除一个节点
		* @param  
		* @retval 
		*/ 
		int single_link_remove(struct single_link *link, Elemtype item)
		{
			if(link == NULL)
				return -1;
	
			//遍历数据
			struct single_link * pNext = link;
			struct single_link * node = NULL;
			while(pNext->next != NULL) //不等于空继续循环
			{
				if(pNext->next->data == item)
					break;
				pNext = pNext->next;
			}

			node = pNext->next;
			pNext->next = pNext->next->next;
			link->data--;
			free(node);
			return 0;
		}

	
	/**
		* @brief  按item大小顺序添加
		* @param  
		* @retval 
		*/ 
		int single_link_Sequential_insert_add(struct single_link *link, Elemtype item)
		{
			//申请一个新节点
			struct single_link *node = NULL;
			node = (struct single_link *)malloc(sizeof(struct single_link));
			if(node == NULL)
				return -1;
				
			node->data = item;		//填充数据

			//遍历数据，找到尾节点
			struct single_link * pNext = link;
			while(pNext->next != NULL && pNext->next->data < item)  //不等于空继续循环,或者item比较小
			{
				pNext = pNext->next;
			}

			//现在执行插入操作
			node->next = pNext->next;
			pNext->next = node;
			link->data++;

			//single_link_bainli(link);
			
			return 0;
		}

		
	/**
		* @brief  获取链表值到数组中
		* @param  
		* @retval 
		*/ 
		int single_link_get(struct single_link *link, Elemtype *item, int buf_len, int *item_len)
		{
			int len = 0;
			if(link == NULL || item == NULL)
				return -1;

			//遍历数据
			struct single_link * pNext = link->next;
			while(pNext != NULL && len<buf_len)	//不等于空继续循环,或者item比较小
			{
				item[len] = pNext->data;
				len++;
				pNext = pNext->next;
			}
			if(item_len)
				*item_len = len;
			return 0;
		}


	/**
		* @brief  删除链表，只剩下头节点
		* @param  
		* @retval 
		*/ 
		int single_link_delete(struct single_link *link)
		{
			if(link == NULL)
				return -1;
	
			//遍历数据
			struct single_link * pNext = link;
			struct single_link * node = NULL;
			while(pNext->next != NULL) //不等于空继续循环
			{
				node = pNext->next;
				pNext->next = pNext->next->next;
				link->data--;
				free(node);
			}
			
			return 0;
		}



	/**
		* @brief  按item大小顺序添加
		* @param  
		* @retval 
		*/ 
		int single_link_length(struct single_link *link)
		{			
			return link->data;
		}



/********************************/
/******* 面试中算法 *************/
/********************************/		
	/**
		* @brief  单链表逆序，普通循环法
		* @param  
		* @retval 
		*/ 
		int single_link_reverse1(struct single_link *link)
		{
			if(link == NULL)
				return -1;
	
			//获取3个指针
			struct single_link *pPrev, *pCur, *pNext;

			//调转指针
			pPrev = NULL;   		//默认开始为NULL
			pPrev = link;			//测试链表是否有环
			pCur = link->next;		

			while(pCur != NULL) 		//判读当前指针不为空
			{
				pNext = pCur->next;
				pCur->next = pPrev;
				pPrev = pCur;
				pCur = pNext;
			}
			
			//处理头节点,把最后一个跨在到头节点下
			link->next = pPrev;
			
			printf("pPrev %p %p %p %p\n", pPrev, pPrev->next, pPrev->next->next, pPrev->next->next->next);
			return 0;
		}
	

	/**
		* @brief  判断单链表是否有环
		* @param  
		* @retval =1表示链表有环，=0表示链表没环
		* @idea	  准备两个指针，一个指针一次后移一个节点，一个指针一次后移两个节点，
				  如果相遇说明链表有环，快的指针会碰到或者超越慢的指针
		*/ 
		int single_link_isCycle(struct single_link *link)
		{
			if(link == NULL)
				return -1;

			//1.申请2个指针
			struct single_link *p1 = link;
			struct single_link *p2 = link;

			//2.开始遍历链表，查询是否有环
			while(p1 && p1->next)
			{
				p1 = p1->next->next;    //一次后移两个节点
				p2 = p2->next;			//一次后移一个节点
				if(p1 == p2)
					return 1;
			}
			
			return 0;
		}


	/**
		* @brief  单链表的环长
		* @param  
		* @retval 环的长度
		*/ 
		int single_link_cycle_len(struct single_link *link)
		{
			if(link == NULL)
				return -1;
	
			//1.申请2个指针
			struct single_link *p1 = link;
			struct single_link *p2 = link;
			int cycle_len = 0, flag = 0;
			
			//2.开始遍历链表，查询是否有环
			while(p1 && p1->next)
			{
				p1 = p1->next->next;	//一次后移两个节点
				p2 = p2->next;			//一次后移一个节点
				if((p1 == p2) || flag)
				{
					if(p1 == p2 && flag)
						break;
					(flag) ? (cycle_len++):(flag=1);
				}
			}
	
			printf("cycle_len = %d\n", cycle_len);
			return cycle_len;
		}


	/**
		* @brief  单链表入环点
		* @param  
		* @retval 入环点
		*/ 
		int single_link_cycle_point(struct single_link *link)
		{
			if(link == NULL)
				return -1;
	
			//1.申请2个指针
			struct single_link *p1 = link;
			struct single_link *p2 = link;
			struct single_link *p3 = link;
			
			//2.开始遍历链表，查询是否有环
			while(p1 && p1->next)
			{
				p1 = p1->next->next;	//一次后移两个节点
				p2 = p2->next;			//一次后移一个节点
				if(p1 == p2)
				{
					break;
				}
			}

			//3.再由一个指针从头节点开始后移，p2指针继续后移两个指针相遇时，就是入环点
			while(p2 && p3)
			{
				p2 = p2->next;
				p3 = p3->next;
				if(p2 == p3)
					break;
			}

			printf("cycle_len = %d\n", p2->data);
			return p2->data;
		}


		
	/**
		* @brief  遍历链表
		* @param  
		* @retval 
		*/ 
		int single_link_bainli(struct single_link *link)
		{
			//遍历数据，找到尾节点
			struct single_link * pNext = link;
			printf("tou %ld ", pNext->data);
			pNext = pNext->next;
			while(pNext != NULL)  //不等于空继续循环
			{
				printf("%ld ", pNext->data);
				pNext = pNext->next;
			}
			
			printf("\n");
			return 0;
		}

		#if 1
		int main()
		{
		    int i = 0;
			int ret = -1;

			struct single_link *g_link = NULL;
			single_link_creat(&g_link);

			single_link_bainli(g_link);

			single_link_head_add(g_link, 22);
			single_link_head_add(g_link, 33);
			single_link_head_add(g_link, 11);
			single_link_head_add(g_link, 55);
			single_link_head_add(g_link, 99);
			single_link_head_add(g_link, 33);
			single_link_head_add(g_link, 67);
			single_link_head_add(g_link, 123);
			
			single_link_bainli(g_link);

			//single_link_remove(g_link, 22);
			single_link_reverse1(g_link);
			ret = single_link_isCycle(g_link);
			printf("ret = %d\n", ret);
			single_link_cycle_len(g_link);
			single_link_cycle_point(g_link);
			//single_link_bainli(g_link);
		    return 0;

		}
		#endif


/**
    * @}
    */


/**
    * @}
    */

/**
    * @}
    */

/**
    * @}
    */

/************************ (C) 2019 HOME 深圳龙华 *****END OF FILE****/

